Simulation for comparing SSH, SSH-SSL, SSH-FL and Seurat, using both Louvain Clustering method and SC3 clustering

Using the R Package Splatter, which uses a Gamma-Poisson model, I simulated scRNA-seq data consisting of 200 cells x 2000 genes 

5 groups (clusters), with probabilities of 0.7,0.1,0.02,0.15 and 0.03, mimicking the population percentages seen in Tabula Sapiens data  Mimicks the rare cell populations seen in real data.

Clustering performance are evaluated using Adjusted Rand Index, which compares predicted clusters with true labels.

##function for SSH 
ari_ssh <- c() 
ari_seurat <- c() 
ari_feastfl <- c() 
ari_sparse <- c() 
ari_scm <- c() 
ari_sc3_ssl <- c() 
ari_sc3_fl <- c() 
ari_sc3_seurat <- c() 
ari_sc3_lasso <- c() 
ari_sc3_scm <- c() 

library(splatter)
library(SCMarker)
library(FEAST)
compare_met <- function(nreps, nogenes, nocells, sc3 = FALSE) { 
for (i in 1:nreps) { 
sim.groups3 <- splatSimulate(nGenes=nogenes, batchCells=nocells, group.prob = c(0.7,0.1,0.02,0.15,0.03), method = "groups",
                             verbose = FALSE) 

Y <- counts(sim.groups3) 

Y <- as.matrix(Y)
library(dplyr)
tot_med <- colSums(Y) %>%
  median()
norm1 <- function(vec) {
  vec/sum(vec)
}
Y <- apply(Y, 2, norm1)
Y <- Y * tot_med
Y <- Y + 0.1
Y <- t(Y) 

Y <- log2(Y - min(Y) + 1)
tb <- tibble(cell = rownames(Y)) %>%
  bind_cols(as_tibble(Y)) 

t <- as.matrix(tb[,-1])
rownames(t) <- tb$cell

# center for each feature
t <- scale(t, scale = FALSE)

# scale so that the overall variance is unit 
t <- t/sd(as.double(t)) 

nperms = 3 
lambda1 <- 0.0001
lambda0s <- seq(0.001, 1000, length = 100)
# 
# # this is the most costly computation in RECOMBINE
#set.seed(1)   ##important!! 
#library(recombine)
out3 <- SHC_SSL_gapstat(x = t,
                        nperms = nperms,
                        lambda0s = lambda0s,
                        lambda1 = lambda1)


w2 <- out3$result$w

names(w2) <- colnames(t)

w2 <- sort(w2, decreasing = TRUE)
w2_nonzero <- w2[w2 > 0]

names <- attr(w2_nonzero, "names")
idxssl3 <- match(names, colnames(t))

data <- counts(sim.groups3) 
data <- CreateSeuratObject(counts = data,
                           min.features = 0,
                           min.cells = 0)
data <- NormalizeData(data)
# set variable genes as all discriminant markers
#VariableFeatures(data) <- rownames(data)
# Scaling the data
sobj <- ScaleData(data, features = rownames(data)) 
# Perform linear dimensional reduction

##For SHC-SSL - 
sobj <- RunPCA(sobj, features = rownames(data)[idxssl3]) 

sobj <- FindNeighbors(sobj, dims=1:20)  
sobj <- FindClusters(sobj) 

trueclass <- colData(sim.groups3)$Group  
ari_ssh[i] <- eval_Cluster(sobj@meta.data$seurat_clusters, trueclass)["ARI"]

####compare seurat 
data <- counts(sim.groups3)
library(Seurat)
data2 <- CreateSeuratObject(counts = data,
                            project = "seurat",
                            min.features = 0,
                            min.cells = 0)
data2 <- FindVariableFeatures(data2, selection.method = "vst", nfeatures = length(idxssl3)) 

all.genes <- rownames(data2) 
data2 <- ScaleData(data2, features=all.genes)
# set variable genes as all discriminant markers
##
data2 <- RunPCA(data2, features=VariableFeatures(data2)) 

data2 <- FindNeighbors(data2, dims=1:20)  
data2 <- FindClusters(data2) #resolution = 1.2) #resolution = 1.08)  #0.76 
trueclass <- colData(sim.groups3)$Group  
ari_seurat[i] <- eval_Cluster(data2@meta.data$seurat_clusters, trueclass)["ARI"]

#LASSO sparse 
shc.permute.out2 <- sparcl::HierarchicalSparseCluster.permute(x = t,
                                                              nperms = 3,
                                                              wbounds = seq(1.1, 10, len = 100))
shc.out2 <- sparcl::HierarchicalSparseCluster(x = t,
                                              wbound = shc.permute.out2$bestw)

w <- shc.out2$ws
names(w) <- colnames(t)
w <- sort(w, decreasing = TRUE)
w_nonzero <- w[w > 0]

names <- attr(w_nonzero, "names")
idxlasso2 <- match(names, colnames(t))

data3 <- counts(sim.groups3) 
data3 <- CreateSeuratObject(counts = data3,
                            min.features = 0,
                            min.cells = 0)
data3 <- NormalizeData(data3)
# set variable genes as all discriminant markers
#VariableFeatures(data) <- rownames(data)
# Scaling the data
data3 <- ScaleData(data3, features = rownames(data3))
# Perform linear dimensional reduction

data3 <- RunPCA(data3, features = rownames(data3)[idxlasso2]) 

pca <- data3[['pca']]  

data3 <- FindNeighbors(data3, dims=1:min(length(pca@stdev),20))   

data3 <- FindClusters(data3) #resolution = 0.76)  
trueclass <- colData(sim.groups3)$Group  
ari_sparse[i] <- eval_Cluster(data3@meta.data$seurat_clusters, trueclass)["ARI"]

#FEAST - FL 
Y <- counts(sim.groups3)
#Y = process_Y(Y) 
ixs = FEAST(Y, k=5)
t2 <- t[, ixs] 

out4 <- SHC_FL_gapstat(t2,
                       lambda1s = seq(0, 0.5*max(nrow(t), ncol(t)), length = 5),
                       lambda2s = seq(1, 10*max(nrow(t), ncol(t)), length = 5),
                       nperms = 3)

w2 <- out4$result$w

names(w2) <- colnames(t2)
w2 <- sort(w2, decreasing = TRUE)
w2_nonzero <- w2[w2 > 0]

names <- attr(w2_nonzero, "names")
idxssl4 <- match(names, colnames(t2))

data4 <- counts(sim.groups3) 
data4 <- CreateSeuratObject(counts = data4,
                           project = "fl",
                           min.features = 0,
                           min.cells = 0)
data4 <- NormalizeData(data4)
# set variable genes as all discriminant markers
#VariableFeatures(data) <- rownames(data)
# Scaling the data
data4 <- ScaleData(data4, features = rownames(data4)) 
# Perform linear dimensional reduction

##For SHC-SSL - 
data4 <- RunPCA(data4, features = rownames(data4)[ixs][idxssl4]) 

data4 <- FindNeighbors(data4, dims=1:20)  
data4 <- FindClusters(data4) 

trueclass <- colData(sim.groups3)$Group 
ari_feastfl[i] <- eval_Cluster(data4@meta.data$seurat_clusters, trueclass)["ARI"]

#SC-Marker 
Y = process_Y(Y) 
res=ModalFilter(data=Y,geneK=10,cellK=10,width=2)# default widt
res=GeneFilter(obj=res)
res=getMarker(obj=res,k=300,n=30)  
head(res$marker)
idxssl6<-match(res$marker, rownames(Y)) 
data6 <- counts(sim.groups3) 
data6 <- CreateSeuratObject(counts = data6,
                            min.features = 0,
                            min.cells = 0)
data6 <- NormalizeData(data6)
# set variable genes as all discriminant markers
#VariableFeatures(data) <- rownames(data)
# Scaling the data
data6 <- ScaleData(data6, features = rownames(data6)) 
# Perform linear dimensional reduction

data6 <- RunPCA(data6, features = rownames(data6)[idxssl6]) 

data6 <- FindNeighbors(data6, dims=1:20)  
data6 <- FindClusters(data6) 

trueclass <- colData(sim.groups3)$Group 
ari_scm[i] <- eval_Cluster(data6@meta.data$seurat_clusters, trueclass)["ARI"]

if (sc3 == TRUE) {
  sobj2 <- counts(sim.groups3)
  #library(FEAST)
  sc3_reslv <- SC3_Clust(sobj2, k=5, input_markers=VariableFeatures(data2)) 
  trueclass <- colData(sim.groups3)$Group  
  ari_sc3_seurat[i] <- eval_Cluster(sc3_reslv$cluster, trueclass)["ARI"]
  
  sc3_reslasso <- SC3_Clust(sobj2, k=5, input_markers=rownames(sobj2)[idxlasso2]) 
  trueclass <- colData(sim.groups3)$Group  
  ari_sc3_lasso[i] <- eval_Cluster(sc3_reslasso$cluster, trueclass)["ARI"]
  
  sc3_res <- SC3_Clust(sobj2, k=5, input_markers=rownames(sobj2)[idxssl3]) 
  trueclass <- colData(sim.groups3)$Group  
  ari_sc3_ssl[i] <- eval_Cluster(sc3_res$cluster, trueclass)["ARI"]
  
  sc3_resfl <- SC3_Clust(sobj2, k=5, input_markers=rownames(sobj2)[ixs][idxssl4]) 
  trueclass <- colData(sim.groups3)$Group  
  ari_sc3_fl[i] <- eval_Cluster(sc3_resfl$cluster, trueclass)["ARI"]
  
  sc3_resscm <- SC3_Clust(sobj2, k=5, input_markers=rownames(sobj2)[idxssl6]) 
  ari_sc3_scm[i] <- eval_Cluster(sc3_resscm$cluster, trueclass)["ARI"]
    } 
} 
results <- list(ari_ssh, ari_seurat, ari_feastfl, ari_sparse, ari_scm, ari_sc3_seurat, ari_sc3_lasso, ari_sc3_ssl, ari_sc3_fl, ari_sc3_scm)   
return(results) 
} 

#doing 10 simulations 
compare_met(100, 2000, 200, sc3 = TRUE) 

# 6 more 

Simulation results

Figure 1 : SHC-SSL and SHC-FL performed better than Seurat and SHC in clustering data with rare cell populations  (due to computation, this is not displayed here, please refer to PPT)

Figure 2: SHC-SSL and SHC-FL similarly performed better than SHC using SC3 clustering  (due to computation, this is not displayed here, please refer to PPT)

Comparing feature selection methods with real data - Tabula Sapiens human kidney cells data

Challenges - 7 cell types : Kidney epithelial cell, B cell, CD4 T cell, CD8 T cell, NK cell, Macropages and Endothelial cell  -> more than 8000 out of 9000 cells are kidney epithelial cells, Seurat performs poorly in clustering rare cell populations 

gap statistic

out <- readRDS("scRNA_shc_ssl_out.rds") 
plot(out$w_l0norm,
     out$gaps_mean,
     log = "x",
     xlab = "# Non-zero Features",
     ylab = "Gap Statistics",
     ylim = c(min(out$gaps_mean - out$gaps_se) - 0.0001,
              max(out$gaps_mean + out$gaps_se) + 0.0001),
     type = "l",
     lwd = 1)
arrows(x0 = out$w_l0norm,
       y0 = out$gaps_mean - out$gaps_se,
       x1 = out$w_l0norm,
       y1 = out$gaps_mean + out$gaps_se,
       code = 3, angle = 90, length = 0.02, lwd = 1)

selecting the non-zero weight features for recombine

w <- out$result$w
names(w) <- colnames(mt_expr)

w <- sort(w, decreasing = TRUE)
w_nonzero <- w[w > 0]

tb <- tibble(feature = names(w),
             w = w)
tb <- tb %>%
  mutate(i = 1:nrow(tb)) %>%
  mutate(label = ifelse(i <= 10, feature, ""))

options(ggrepel.max.overlaps = Inf)
ggline(tb, "i", "w",
            xlab = "feature index",
            label = "label",
            repel = TRUE,
            label.rectangle = TRUE,
            point.size = 0.1,
            plot_type = "p")

Seurat’s built in feature selection method (vst)

library(Seurat)
#normalize 
kidata <- NormalizeData(kidata)

#now, use blood1 for HVF selected by Seurat, and blood2 for ones selected by FEAST
kidata <- FindVariableFeatures(kidata, selection.method = "vst", nfeatures = 2000)

all.genes <- rownames(kidata) 
kidata <- ScaleData(kidata, features=all.genes)
#if using FEAST should input selected features here 
kidata1 <- RunPCA(kidata, features=VariableFeatures(object=kidata))
ElbowPlot(kidata1) #use 18 PCs 
kidata1 <- FindNeighbors(kidata1, dims=1:15)

kidata1 <- FindClusters(kidata1, resolution = 0.18) 
trueclass <- kidata@meta.data$free_annotation

evaluating the performance of Seurat’s built in feature selection method (vst)

library(FEAST)
ki_seurat<-eval_Cluster(kidata1@meta.data$seurat_clusters, trueclass) 

library(knitr)
kable(ki_seurat, caption = "Cluster Evaluation Metrics")
Cluster Evaluation Metrics
x
ARI 0.2996862
Purity 0.9539467
Jaccard 0.4672912
FM 0.6821978

UMAP (with true labels)

#set.seed(1)
#kidata1 <- RunUMAP(kidata1, dims=1:50) 
DimPlot(kidata1, reduction="umap")

# Step 1: Add true class and clustering labels to the metadata
kidata1$trueclass <- kidata1@meta.data$free_annotation

# Step 2: Extract UMAP coordinates and metadata
umap_data <- as.data.frame(Embeddings(kidata1, "umap"))  # Extract UMAP embeddings
colnames(umap_data) <- c("UMAP_1", "UMAP_2")             # Rename columns
umap_data$seurat_clusters <- kidata1$seurat_clusters      # Add cluster labels
umap_data$trueclass <- kidata1$trueclass                  # Add true class labels

# Step 3: Plot UMAP with overlayed true class labels
ggplot(umap_data, aes(x = UMAP_1, y = UMAP_2)) +
  geom_point(aes(color = as.factor(seurat_clusters)), alpha = 0.6, size = 2) + # Points for clusters
  geom_text(aes(label = trueclass), size = 3, vjust = -1, check_overlap = TRUE) + # Text overlay for true class
  labs(
    color = "Cluster", 
    x = "UMAP 1",
    y = "UMAP 2",
    title = "UMAP: Clustering Results with True Class Overlay"
  ) +
  theme_minimal() +
  theme(
    legend.position = "right",          # Adjust legend position
    plot.title = element_text(hjust = 0.5)  # Center the title
  )

Sparse Hierarchial Clustering (SHC)

#normalize 
Y1 <- as.matrix(Y1)

library(dplyr)
tot_med <- colSums(Y1) %>%
  median()
norm1 <- function(vec) {
  vec/sum(vec)
}
Y1 <- apply(Y1, 2, norm1)
Y1 <- Y1 * tot_med
Y1 <- Y1 + 0.1
Y1 <- t(Y1) 

Y1 <- log2(Y1 - min(Y1) + 1)
tb <- tibble(cell = rownames(Y1)) %>%
  bind_cols(as_tibble(Y1)) 

t <- as.matrix(tb[,-1])
rownames(t) <- tb$cell

# center for each feature
t <- scale(t, scale = FALSE)

# scale so that the overall variance is unit 
t <- t/sd(as.double(t)) 
dim(t)
View(t)

shc.permute.out <- sparcl::HierarchicalSparseCluster.permute(x = t,
                                                             nperms = 3,
                                                             wbounds = seq(1.1, 10, len = 100))


w3 <- shc.permute.out$result$w

names(w3) <- colnames(t)

w3 <- sort(w3, decreasing = TRUE)
w3_nonzero <- w3[w3 > 0]

names <- attr(w3_nonzero, "names")
idxssl4 <- match(names, rownames(Y))
length(idxssl4) 
#data <- counts(sim.groups3) 
library(Seurat)

data <- CreateSeuratObject(counts = Y,
                           min.features = 0,
                           min.cells = 0)
data <- NormalizeData(data)
# set variable genes as all discriminant markers
#VariableFeatures(data) <- rownames(data)
# Scaling the data
sobj <- ScaleData(data, features = rownames(data)) 
# Perform linear dimensional reduction

##For SHC-SSL - 
kidata4 <- RunPCA(sobj, features = rownames(data)[idxssl4]) 

kidata4 <- FindNeighbors(kidata2, dims=1:20)  
kidata4 <- FindClusters(kidata2, resolution=0.16)

kidata4$trueclass <- kidata1@meta.data$free_annotation

ki_shc<-eval_Cluster(kidata4@meta.data$seurat_clusters, trueclass)
kidata4 <- FindNeighbors(kidata4, dims=1:15)
kidata4 <- FindClusters(kidata4, resolution = 0.12) 
trueclass <- kidata@meta.data$free_annotation

evaluating performance with SHC

library(FEAST)
ki_shc<-eval_Cluster(kidata4@meta.data$seurat_clusters, trueclass) 

library(knitr)
kable(ki_shc, caption = "Cluster Evaluation Metrics")
Cluster Evaluation Metrics
x
ARI 0.2218051
Purity 0.9497977
Jaccard 0.3731324
FM 0.6082610

UMAP (with true labels)

set.seed(1)
kidata4 <- RunUMAP(kidata4, dims=1:50) 
DimPlot(kidata4, reduction="umap") 

library(ggplot2)
# Step 1: Add true class and clustering labels to the metadata
kidata4$trueclass <- kidata1@meta.data$free_annotation

# Step 2: Extract UMAP coordinates and metadata
umap_data <- as.data.frame(Embeddings(kidata4, "umap"))  # Extract UMAP embeddings
colnames(umap_data) <- c("UMAP_1", "UMAP_2")             # Rename columns
umap_data$seurat_clusters <- kidata4$seurat_clusters      # Add cluster labels
umap_data$trueclass <- kidata4$trueclass                  # Add true class labels

# Step 3: Plot UMAP with overlayed true class labels
ggplot(umap_data, aes(x = UMAP_1, y = UMAP_2)) +
  geom_point(aes(color = as.factor(seurat_clusters)), alpha = 0.6, size = 2) + # Points for clusters
  geom_text(aes(label = trueclass), size = 3, vjust = -1, check_overlap = TRUE) + # Text overlay for true class
  labs(
    color = "Cluster", 
    x = "UMAP 1",
    y = "UMAP 2",
    title = "UMAP: Clustering Results with True Class Overlay"
  ) +
  theme_minimal() +
  theme(
    legend.position = "right",          # Adjust legend position
    plot.title = element_text(hjust = 0.5)  # Center the title
  )

RECOMBINE SHC-SSL algorithm

#normalize 
Y1 <- as.matrix(Y1)

library(dplyr)
tot_med <- colSums(Y1) %>%
  median()
norm1 <- function(vec) {
  vec/sum(vec)
}
Y1 <- apply(Y1, 2, norm1)
Y1 <- Y1 * tot_med
Y1 <- Y1 + 0.1
Y1 <- t(Y1) 

Y1 <- log2(Y1 - min(Y1) + 1)
tb <- tibble(cell = rownames(Y1)) %>%
  bind_cols(as_tibble(Y1)) 

t <- as.matrix(tb[,-1])
rownames(t) <- tb$cell

# center for each feature
t <- scale(t, scale = FALSE)

# scale so that the overall variance is unit 
t <- t/sd(as.double(t)) 
dim(t)
View(t)

nperms = 3 
lambda1 <- 0.0001
lambda0s <- seq(0.001, 1000, length = 100)
library(recombine) 
# 
# # this is the most costly computation in RECOMBINE
#set.seed(1)   ##important!! 
library(recombine)
out3 <- SHC_SSL_gapstat(x = t,
                        nperms = nperms,
                        lambda0s = lambda0s,
                        lambda1 = lambda1)


w2 <- out3$result$w

names(w2) <- colnames(t)

w2 <- sort(w2, decreasing = TRUE)
w2_nonzero <- w2[w2 > 0]

names <- attr(w2_nonzero, "names")
idxssl3 <- match(names, rownames(Y))
length(idxssl3)
#data <- counts(sim.groups3) 
library(Seurat)

data <- CreateSeuratObject(counts = Y,
                           min.features = 0,
                           min.cells = 0)
data <- NormalizeData(data)
# set variable genes as all discriminant markers
#VariableFeatures(data) <- rownames(data)
# Scaling the data
sobj <- ScaleData(data, features = rownames(data)) 
# Perform linear dimensional reduction

##For SHC-SSL - 
kidata2 <- RunPCA(sobj, features = rownames(data)[idxssl3]) 

kidata2 <- FindNeighbors(kidata2, dims=1:20)  
kidata2 <- FindClusters(kidata2, resolution=0.16)

kidata2$trueclass <- kidata1@meta.data$free_annotation

ki_recombine<-eval_Cluster(kidata2@meta.data$seurat_clusters, trueclass)

evaluating SHC-SSL performance

kable(ki_recombine, caption = "Cluster Evaluation Metrics")  
Cluster Evaluation Metrics
x
ARI 0.8176945
Purity 0.9533243
Jaccard 0.9011177
FM 0.9490565

UMAP (with true labels)

kidata3 <- RunUMAP(kidata3, features=rownames(data)[idxssl3]) 
DimPlot(kidata3, reduction="umap") 

# Step 1: Add true class and clustering labels to the metadata
kidata3$trueclass <- kidata1@meta.data$free_annotation

# Step 2: Extract UMAP coordinates and metadata
umap_data <- as.data.frame(Embeddings(kidata3, "umap"))  # Extract UMAP embeddings
colnames(umap_data) <- c("UMAP_1", "UMAP_2")             # Rename columns
umap_data$seurat_clusters <- kidata3$seurat_clusters      # Add cluster labels
umap_data$trueclass <- kidata3$trueclass                  # Add true class labels

# Step 3: Plot UMAP with overlayed true class labels
ggplot(umap_data, aes(x = UMAP_1, y = UMAP_2)) +
  geom_point(aes(color = as.factor(seurat_clusters)), alpha = 0.6, size = 2) + # Points for clusters
  geom_text(aes(label = trueclass), size = 3, vjust = -1, check_overlap = TRUE) + # Text overlay for true class
  labs(
    color = "Cluster", 
    x = "UMAP 1",
    y = "UMAP 2",
    title = "UMAP: Clustering Results with True Class Overlay"
  ) +
  theme_minimal() +
  theme(
    legend.position = "right",          # Adjust legend position
    plot.title = element_text(hjust = 0.5)  # Center the title
  ) 

SCMarker algorithm

library(SCMarker)
dim(Y) 
Y1<-log(Y+1) 

res=ModalFilter(data=Y1,geneK=10,cellK=10,width=2) 
res=GeneFilter(obj=res)
res=getMarker(obj=res,k=300,n=30) 
head(res$marker) 
length(res$marker) #938 

evaluating performance of SCMarker

kidata3 <- RunPCA(kidata2, features = res$marker) 

kidata3 <- FindNeighbors(kidata3, dims=1:20)  
kidata3 <- FindClusters(kidata3, resolution = 0.12)
kidata3$trueclass <- kidata1@meta.data$free_annotation
ki_scmarker<-eval_Cluster(kidata3@meta.data$seurat_clusters, kidata3$trueclass)
#kidata2$trueclass <- kidata1@meta.data$free_annotation
#ki_recombine<-eval_Cluster(kidata2@meta.data$seurat_clusters, trueclass) 
kable(ki_scmarker, caption = "Cluster Evaluation Metrics") 
Cluster Evaluation Metrics
x
ARI 0.8940461
Purity 0.9537392
Jaccard 0.9446944
FM 0.9718630

UMAP (with true labels)

#kidata2 <- RunUMAP(kidata2, features=genes) 
DimPlot(kidata2, reduction="umap") 

# Step 1: Add true class and clustering labels to the metadata
kidata2$trueclass <- kidata1@meta.data$free_annotation

# Step 2: Extract UMAP coordinates and metadata
umap_data <- as.data.frame(Embeddings(kidata2, "umap"))  # Extract UMAP embeddings
colnames(umap_data) <- c("UMAP_1", "UMAP_2")             # Rename columns
umap_data$seurat_clusters <- kidata2$seurat_clusters      # Add cluster labels
umap_data$trueclass <- kidata2$trueclass                  # Add true class labels

# Step 3: Plot UMAP with overlayed true class labels
ggplot(umap_data, aes(x = UMAP_1, y = UMAP_2)) +
  geom_point(aes(color = as.factor(seurat_clusters)), alpha = 0.6, size = 2) + # Points for clusters
  geom_text(aes(label = trueclass), size = 3, vjust = -1, check_overlap = TRUE) + # Text overlay for true class
  labs(
    color = "Cluster", 
    x = "UMAP 1",
    y = "UMAP 2",
    title = "UMAP: Clustering Results with True Class Overlay"
  ) +
  theme_minimal() +
  theme(
    legend.position = "right",          # Adjust legend position
    plot.title = element_text(hjust = 0.5)  # Center the title
  ) 

Compare the four methods in clustering accuracy

res_compare<-cbind(ki_seurat, ki_recombine, ki_scmarker, ki_shc) 
kable(res_compare, caption = "Cluster Evaluation Metrics") 
Cluster Evaluation Metrics
ki_seurat ki_recombine ki_scmarker ki_shc
ARI 0.2996862 0.8176945 0.8940461 0.2218051
Purity 0.9539467 0.9533243 0.9537392 0.9497977
Jaccard 0.4672912 0.9011177 0.9446944 0.3731324
FM 0.6821978 0.9490565 0.9718630 0.6082610

It is shown that the SHC-SSL feature selection algorithm outperforms both Seurat and traditional SHC, and it is comparable to the SCMarker algorithm.

LS0tCnRpdGxlOiBJZGVudGlmeWluZyByYXJlIGNlbGwgcG9wdWxhdGlvbnMgYW5kIGltcHJvdmluZyBjbHVzdGVyaW5nIGFjY3VyYWN5IHVzaW5nIFJFQ09NQklORSBhbGdvcml0aG0Kc3VidGl0bGU6IFNpbXVsYXRpb24gYW5kIHJlYWwgZGF0YSBhbmFseXNpcyAKYXV0aG9yOiBXYW5ydSBHdW8gCmRhdGU6ICJMYXN0IGNvbXBpbGVkIG9uIGByIGZvcm1hdChTeXMudGltZSgpLCAnJUIgJWQsICVZJylgIgpvdXRwdXQ6CiAgaHRtbF9ub3RlYm9vazogCiAgICB0b2M6IHllcwogICAgdG9jX2RlcHRoOiA0CiAgICB0b2NfZmxvYXQ6IHllcwotLS0KCiMgU2ltdWxhdGlvbiBmb3IgY29tcGFyaW5nIFNTSCwgU1NILVNTTCwgU1NILUZMIGFuZCBTZXVyYXQsIHVzaW5nIGJvdGggTG91dmFpbiBDbHVzdGVyaW5nIG1ldGhvZCBhbmQgU0MzIGNsdXN0ZXJpbmcgClVzaW5nIHRoZSBSIFBhY2thZ2UgU3BsYXR0ZXIsIHdoaWNoIHVzZXMgYSBHYW1tYS1Qb2lzc29uIG1vZGVsLCBJIHNpbXVsYXRlZCBzY1JOQS1zZXEgZGF0YSBjb25zaXN0aW5nIG9mIDIwMCBjZWxscyB4IDIwMDAgZ2VuZXPCoAoKNSBncm91cHMgKGNsdXN0ZXJzKSwgd2l0aCBwcm9iYWJpbGl0aWVzIG9mIDAuNywwLjEsMC4wMiwwLjE1IGFuZCAwLjAzLCBtaW1pY2tpbmcgdGhlIHBvcHVsYXRpb24gcGVyY2VudGFnZXMgc2VlbiBpbiBUYWJ1bGEgU2FwaWVucyBkYXRhwqAKTWltaWNrcyB0aGUgcmFyZSBjZWxsIHBvcHVsYXRpb25zIHNlZW4gaW4gcmVhbCBkYXRhLiAKCkNsdXN0ZXJpbmcgcGVyZm9ybWFuY2UgYXJlIGV2YWx1YXRlZCB1c2luZyBBZGp1c3RlZCBSYW5kIEluZGV4LCB3aGljaCBjb21wYXJlcyBwcmVkaWN0ZWQgY2x1c3RlcnMgd2l0aCB0cnVlIGxhYmVscy4gCgpgYGB7cn0KIyNmdW5jdGlvbiBmb3IgU1NIIAphcmlfc3NoIDwtIGMoKSAKYXJpX3NldXJhdCA8LSBjKCkgCmFyaV9mZWFzdGZsIDwtIGMoKSAKYXJpX3NwYXJzZSA8LSBjKCkgCmFyaV9zY20gPC0gYygpIAphcmlfc2MzX3NzbCA8LSBjKCkgCmFyaV9zYzNfZmwgPC0gYygpIAphcmlfc2MzX3NldXJhdCA8LSBjKCkgCmFyaV9zYzNfbGFzc28gPC0gYygpIAphcmlfc2MzX3NjbSA8LSBjKCkgCgpsaWJyYXJ5KHNwbGF0dGVyKQpsaWJyYXJ5KFNDTWFya2VyKQpsaWJyYXJ5KEZFQVNUKQpjb21wYXJlX21ldCA8LSBmdW5jdGlvbihucmVwcywgbm9nZW5lcywgbm9jZWxscywgc2MzID0gRkFMU0UpIHsgCmZvciAoaSBpbiAxOm5yZXBzKSB7IApzaW0uZ3JvdXBzMyA8LSBzcGxhdFNpbXVsYXRlKG5HZW5lcz1ub2dlbmVzLCBiYXRjaENlbGxzPW5vY2VsbHMsIGdyb3VwLnByb2IgPSBjKDAuNywwLjEsMC4wMiwwLjE1LDAuMDMpLCBtZXRob2QgPSAiZ3JvdXBzIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICB2ZXJib3NlID0gRkFMU0UpIAoKWSA8LSBjb3VudHMoc2ltLmdyb3VwczMpIAoKWSA8LSBhcy5tYXRyaXgoWSkKbGlicmFyeShkcGx5cikKdG90X21lZCA8LSBjb2xTdW1zKFkpICU+JQogIG1lZGlhbigpCm5vcm0xIDwtIGZ1bmN0aW9uKHZlYykgewogIHZlYy9zdW0odmVjKQp9ClkgPC0gYXBwbHkoWSwgMiwgbm9ybTEpClkgPC0gWSAqIHRvdF9tZWQKWSA8LSBZICsgMC4xClkgPC0gdChZKSAKClkgPC0gbG9nMihZIC0gbWluKFkpICsgMSkKdGIgPC0gdGliYmxlKGNlbGwgPSByb3duYW1lcyhZKSkgJT4lCiAgYmluZF9jb2xzKGFzX3RpYmJsZShZKSkgCgp0IDwtIGFzLm1hdHJpeCh0YlssLTFdKQpyb3duYW1lcyh0KSA8LSB0YiRjZWxsCgojIGNlbnRlciBmb3IgZWFjaCBmZWF0dXJlCnQgPC0gc2NhbGUodCwgc2NhbGUgPSBGQUxTRSkKCiMgc2NhbGUgc28gdGhhdCB0aGUgb3ZlcmFsbCB2YXJpYW5jZSBpcyB1bml0IAp0IDwtIHQvc2QoYXMuZG91YmxlKHQpKSAKCm5wZXJtcyA9IDMgCmxhbWJkYTEgPC0gMC4wMDAxCmxhbWJkYTBzIDwtIHNlcSgwLjAwMSwgMTAwMCwgbGVuZ3RoID0gMTAwKQojIAojICMgdGhpcyBpcyB0aGUgbW9zdCBjb3N0bHkgY29tcHV0YXRpb24gaW4gUkVDT01CSU5FCiNzZXQuc2VlZCgxKSAgICMjaW1wb3J0YW50ISEgCiNsaWJyYXJ5KHJlY29tYmluZSkKb3V0MyA8LSBTSENfU1NMX2dhcHN0YXQoeCA9IHQsCiAgICAgICAgICAgICAgICAgICAgICAgIG5wZXJtcyA9IG5wZXJtcywKICAgICAgICAgICAgICAgICAgICAgICAgbGFtYmRhMHMgPSBsYW1iZGEwcywKICAgICAgICAgICAgICAgICAgICAgICAgbGFtYmRhMSA9IGxhbWJkYTEpCgoKdzIgPC0gb3V0MyRyZXN1bHQkdwoKbmFtZXModzIpIDwtIGNvbG5hbWVzKHQpCgp3MiA8LSBzb3J0KHcyLCBkZWNyZWFzaW5nID0gVFJVRSkKdzJfbm9uemVybyA8LSB3Mlt3MiA+IDBdCgpuYW1lcyA8LSBhdHRyKHcyX25vbnplcm8sICJuYW1lcyIpCmlkeHNzbDMgPC0gbWF0Y2gobmFtZXMsIGNvbG5hbWVzKHQpKQoKZGF0YSA8LSBjb3VudHMoc2ltLmdyb3VwczMpIApkYXRhIDwtIENyZWF0ZVNldXJhdE9iamVjdChjb3VudHMgPSBkYXRhLAogICAgICAgICAgICAgICAgICAgICAgICAgICBtaW4uZmVhdHVyZXMgPSAwLAogICAgICAgICAgICAgICAgICAgICAgICAgICBtaW4uY2VsbHMgPSAwKQpkYXRhIDwtIE5vcm1hbGl6ZURhdGEoZGF0YSkKIyBzZXQgdmFyaWFibGUgZ2VuZXMgYXMgYWxsIGRpc2NyaW1pbmFudCBtYXJrZXJzCiNWYXJpYWJsZUZlYXR1cmVzKGRhdGEpIDwtIHJvd25hbWVzKGRhdGEpCiMgU2NhbGluZyB0aGUgZGF0YQpzb2JqIDwtIFNjYWxlRGF0YShkYXRhLCBmZWF0dXJlcyA9IHJvd25hbWVzKGRhdGEpKSAKIyBQZXJmb3JtIGxpbmVhciBkaW1lbnNpb25hbCByZWR1Y3Rpb24KCiMjRm9yIFNIQy1TU0wgLSAKc29iaiA8LSBSdW5QQ0Eoc29iaiwgZmVhdHVyZXMgPSByb3duYW1lcyhkYXRhKVtpZHhzc2wzXSkgCgpzb2JqIDwtIEZpbmROZWlnaGJvcnMoc29iaiwgZGltcz0xOjIwKSAgCnNvYmogPC0gRmluZENsdXN0ZXJzKHNvYmopIAoKdHJ1ZWNsYXNzIDwtIGNvbERhdGEoc2ltLmdyb3VwczMpJEdyb3VwICAKYXJpX3NzaFtpXSA8LSBldmFsX0NsdXN0ZXIoc29iakBtZXRhLmRhdGEkc2V1cmF0X2NsdXN0ZXJzLCB0cnVlY2xhc3MpWyJBUkkiXQoKIyMjI2NvbXBhcmUgc2V1cmF0IApkYXRhIDwtIGNvdW50cyhzaW0uZ3JvdXBzMykKbGlicmFyeShTZXVyYXQpCmRhdGEyIDwtIENyZWF0ZVNldXJhdE9iamVjdChjb3VudHMgPSBkYXRhLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJvamVjdCA9ICJzZXVyYXQiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgbWluLmZlYXR1cmVzID0gMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbi5jZWxscyA9IDApCmRhdGEyIDwtIEZpbmRWYXJpYWJsZUZlYXR1cmVzKGRhdGEyLCBzZWxlY3Rpb24ubWV0aG9kID0gInZzdCIsIG5mZWF0dXJlcyA9IGxlbmd0aChpZHhzc2wzKSkgCgphbGwuZ2VuZXMgPC0gcm93bmFtZXMoZGF0YTIpIApkYXRhMiA8LSBTY2FsZURhdGEoZGF0YTIsIGZlYXR1cmVzPWFsbC5nZW5lcykKIyBzZXQgdmFyaWFibGUgZ2VuZXMgYXMgYWxsIGRpc2NyaW1pbmFudCBtYXJrZXJzCiMjCmRhdGEyIDwtIFJ1blBDQShkYXRhMiwgZmVhdHVyZXM9VmFyaWFibGVGZWF0dXJlcyhkYXRhMikpIAoKZGF0YTIgPC0gRmluZE5laWdoYm9ycyhkYXRhMiwgZGltcz0xOjIwKSAgCmRhdGEyIDwtIEZpbmRDbHVzdGVycyhkYXRhMikgI3Jlc29sdXRpb24gPSAxLjIpICNyZXNvbHV0aW9uID0gMS4wOCkgICMwLjc2IAp0cnVlY2xhc3MgPC0gY29sRGF0YShzaW0uZ3JvdXBzMykkR3JvdXAgIAphcmlfc2V1cmF0W2ldIDwtIGV2YWxfQ2x1c3RlcihkYXRhMkBtZXRhLmRhdGEkc2V1cmF0X2NsdXN0ZXJzLCB0cnVlY2xhc3MpWyJBUkkiXQoKI0xBU1NPIHNwYXJzZSAKc2hjLnBlcm11dGUub3V0MiA8LSBzcGFyY2w6OkhpZXJhcmNoaWNhbFNwYXJzZUNsdXN0ZXIucGVybXV0ZSh4ID0gdCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBucGVybXMgPSAzLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHdib3VuZHMgPSBzZXEoMS4xLCAxMCwgbGVuID0gMTAwKSkKc2hjLm91dDIgPC0gc3BhcmNsOjpIaWVyYXJjaGljYWxTcGFyc2VDbHVzdGVyKHggPSB0LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgd2JvdW5kID0gc2hjLnBlcm11dGUub3V0MiRiZXN0dykKCncgPC0gc2hjLm91dDIkd3MKbmFtZXModykgPC0gY29sbmFtZXModCkKdyA8LSBzb3J0KHcsIGRlY3JlYXNpbmcgPSBUUlVFKQp3X25vbnplcm8gPC0gd1t3ID4gMF0KCm5hbWVzIDwtIGF0dHIod19ub256ZXJvLCAibmFtZXMiKQppZHhsYXNzbzIgPC0gbWF0Y2gobmFtZXMsIGNvbG5hbWVzKHQpKQoKZGF0YTMgPC0gY291bnRzKHNpbS5ncm91cHMzKSAKZGF0YTMgPC0gQ3JlYXRlU2V1cmF0T2JqZWN0KGNvdW50cyA9IGRhdGEzLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgbWluLmZlYXR1cmVzID0gMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbi5jZWxscyA9IDApCmRhdGEzIDwtIE5vcm1hbGl6ZURhdGEoZGF0YTMpCiMgc2V0IHZhcmlhYmxlIGdlbmVzIGFzIGFsbCBkaXNjcmltaW5hbnQgbWFya2VycwojVmFyaWFibGVGZWF0dXJlcyhkYXRhKSA8LSByb3duYW1lcyhkYXRhKQojIFNjYWxpbmcgdGhlIGRhdGEKZGF0YTMgPC0gU2NhbGVEYXRhKGRhdGEzLCBmZWF0dXJlcyA9IHJvd25hbWVzKGRhdGEzKSkKIyBQZXJmb3JtIGxpbmVhciBkaW1lbnNpb25hbCByZWR1Y3Rpb24KCmRhdGEzIDwtIFJ1blBDQShkYXRhMywgZmVhdHVyZXMgPSByb3duYW1lcyhkYXRhMylbaWR4bGFzc28yXSkgCgpwY2EgPC0gZGF0YTNbWydwY2EnXV0gIAoKZGF0YTMgPC0gRmluZE5laWdoYm9ycyhkYXRhMywgZGltcz0xOm1pbihsZW5ndGgocGNhQHN0ZGV2KSwyMCkpICAgCgpkYXRhMyA8LSBGaW5kQ2x1c3RlcnMoZGF0YTMpICNyZXNvbHV0aW9uID0gMC43NikgIAp0cnVlY2xhc3MgPC0gY29sRGF0YShzaW0uZ3JvdXBzMykkR3JvdXAgIAphcmlfc3BhcnNlW2ldIDwtIGV2YWxfQ2x1c3RlcihkYXRhM0BtZXRhLmRhdGEkc2V1cmF0X2NsdXN0ZXJzLCB0cnVlY2xhc3MpWyJBUkkiXQoKI0ZFQVNUIC0gRkwgClkgPC0gY291bnRzKHNpbS5ncm91cHMzKQojWSA9IHByb2Nlc3NfWShZKSAKaXhzID0gRkVBU1QoWSwgaz01KQp0MiA8LSB0WywgaXhzXSAKCm91dDQgPC0gU0hDX0ZMX2dhcHN0YXQodDIsCiAgICAgICAgICAgICAgICAgICAgICAgbGFtYmRhMXMgPSBzZXEoMCwgMC41Km1heChucm93KHQpLCBuY29sKHQpKSwgbGVuZ3RoID0gNSksCiAgICAgICAgICAgICAgICAgICAgICAgbGFtYmRhMnMgPSBzZXEoMSwgMTAqbWF4KG5yb3codCksIG5jb2wodCkpLCBsZW5ndGggPSA1KSwKICAgICAgICAgICAgICAgICAgICAgICBucGVybXMgPSAzKQoKdzIgPC0gb3V0NCRyZXN1bHQkdwoKbmFtZXModzIpIDwtIGNvbG5hbWVzKHQyKQp3MiA8LSBzb3J0KHcyLCBkZWNyZWFzaW5nID0gVFJVRSkKdzJfbm9uemVybyA8LSB3Mlt3MiA+IDBdCgpuYW1lcyA8LSBhdHRyKHcyX25vbnplcm8sICJuYW1lcyIpCmlkeHNzbDQgPC0gbWF0Y2gobmFtZXMsIGNvbG5hbWVzKHQyKSkKCmRhdGE0IDwtIGNvdW50cyhzaW0uZ3JvdXBzMykgCmRhdGE0IDwtIENyZWF0ZVNldXJhdE9iamVjdChjb3VudHMgPSBkYXRhNCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJvamVjdCA9ICJmbCIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbi5mZWF0dXJlcyA9IDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbi5jZWxscyA9IDApCmRhdGE0IDwtIE5vcm1hbGl6ZURhdGEoZGF0YTQpCiMgc2V0IHZhcmlhYmxlIGdlbmVzIGFzIGFsbCBkaXNjcmltaW5hbnQgbWFya2VycwojVmFyaWFibGVGZWF0dXJlcyhkYXRhKSA8LSByb3duYW1lcyhkYXRhKQojIFNjYWxpbmcgdGhlIGRhdGEKZGF0YTQgPC0gU2NhbGVEYXRhKGRhdGE0LCBmZWF0dXJlcyA9IHJvd25hbWVzKGRhdGE0KSkgCiMgUGVyZm9ybSBsaW5lYXIgZGltZW5zaW9uYWwgcmVkdWN0aW9uCgojI0ZvciBTSEMtU1NMIC0gCmRhdGE0IDwtIFJ1blBDQShkYXRhNCwgZmVhdHVyZXMgPSByb3duYW1lcyhkYXRhNClbaXhzXVtpZHhzc2w0XSkgCgpkYXRhNCA8LSBGaW5kTmVpZ2hib3JzKGRhdGE0LCBkaW1zPTE6MjApICAKZGF0YTQgPC0gRmluZENsdXN0ZXJzKGRhdGE0KSAKCnRydWVjbGFzcyA8LSBjb2xEYXRhKHNpbS5ncm91cHMzKSRHcm91cCAKYXJpX2ZlYXN0ZmxbaV0gPC0gZXZhbF9DbHVzdGVyKGRhdGE0QG1ldGEuZGF0YSRzZXVyYXRfY2x1c3RlcnMsIHRydWVjbGFzcylbIkFSSSJdCgojU0MtTWFya2VyIApZID0gcHJvY2Vzc19ZKFkpIApyZXM9TW9kYWxGaWx0ZXIoZGF0YT1ZLGdlbmVLPTEwLGNlbGxLPTEwLHdpZHRoPTIpIyBkZWZhdWx0IHdpZHQKcmVzPUdlbmVGaWx0ZXIob2JqPXJlcykKcmVzPWdldE1hcmtlcihvYmo9cmVzLGs9MzAwLG49MzApICAKaGVhZChyZXMkbWFya2VyKQppZHhzc2w2PC1tYXRjaChyZXMkbWFya2VyLCByb3duYW1lcyhZKSkgCmRhdGE2IDwtIGNvdW50cyhzaW0uZ3JvdXBzMykgCmRhdGE2IDwtIENyZWF0ZVNldXJhdE9iamVjdChjb3VudHMgPSBkYXRhNiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbi5mZWF0dXJlcyA9IDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBtaW4uY2VsbHMgPSAwKQpkYXRhNiA8LSBOb3JtYWxpemVEYXRhKGRhdGE2KQojIHNldCB2YXJpYWJsZSBnZW5lcyBhcyBhbGwgZGlzY3JpbWluYW50IG1hcmtlcnMKI1ZhcmlhYmxlRmVhdHVyZXMoZGF0YSkgPC0gcm93bmFtZXMoZGF0YSkKIyBTY2FsaW5nIHRoZSBkYXRhCmRhdGE2IDwtIFNjYWxlRGF0YShkYXRhNiwgZmVhdHVyZXMgPSByb3duYW1lcyhkYXRhNikpIAojIFBlcmZvcm0gbGluZWFyIGRpbWVuc2lvbmFsIHJlZHVjdGlvbgoKZGF0YTYgPC0gUnVuUENBKGRhdGE2LCBmZWF0dXJlcyA9IHJvd25hbWVzKGRhdGE2KVtpZHhzc2w2XSkgCgpkYXRhNiA8LSBGaW5kTmVpZ2hib3JzKGRhdGE2LCBkaW1zPTE6MjApICAKZGF0YTYgPC0gRmluZENsdXN0ZXJzKGRhdGE2KSAKCnRydWVjbGFzcyA8LSBjb2xEYXRhKHNpbS5ncm91cHMzKSRHcm91cCAKYXJpX3NjbVtpXSA8LSBldmFsX0NsdXN0ZXIoZGF0YTZAbWV0YS5kYXRhJHNldXJhdF9jbHVzdGVycywgdHJ1ZWNsYXNzKVsiQVJJIl0KCmlmIChzYzMgPT0gVFJVRSkgewogIHNvYmoyIDwtIGNvdW50cyhzaW0uZ3JvdXBzMykKICAjbGlicmFyeShGRUFTVCkKICBzYzNfcmVzbHYgPC0gU0MzX0NsdXN0KHNvYmoyLCBrPTUsIGlucHV0X21hcmtlcnM9VmFyaWFibGVGZWF0dXJlcyhkYXRhMikpIAogIHRydWVjbGFzcyA8LSBjb2xEYXRhKHNpbS5ncm91cHMzKSRHcm91cCAgCiAgYXJpX3NjM19zZXVyYXRbaV0gPC0gZXZhbF9DbHVzdGVyKHNjM19yZXNsdiRjbHVzdGVyLCB0cnVlY2xhc3MpWyJBUkkiXQogIAogIHNjM19yZXNsYXNzbyA8LSBTQzNfQ2x1c3Qoc29iajIsIGs9NSwgaW5wdXRfbWFya2Vycz1yb3duYW1lcyhzb2JqMilbaWR4bGFzc28yXSkgCiAgdHJ1ZWNsYXNzIDwtIGNvbERhdGEoc2ltLmdyb3VwczMpJEdyb3VwICAKICBhcmlfc2MzX2xhc3NvW2ldIDwtIGV2YWxfQ2x1c3RlcihzYzNfcmVzbGFzc28kY2x1c3RlciwgdHJ1ZWNsYXNzKVsiQVJJIl0KICAKICBzYzNfcmVzIDwtIFNDM19DbHVzdChzb2JqMiwgaz01LCBpbnB1dF9tYXJrZXJzPXJvd25hbWVzKHNvYmoyKVtpZHhzc2wzXSkgCiAgdHJ1ZWNsYXNzIDwtIGNvbERhdGEoc2ltLmdyb3VwczMpJEdyb3VwICAKICBhcmlfc2MzX3NzbFtpXSA8LSBldmFsX0NsdXN0ZXIoc2MzX3JlcyRjbHVzdGVyLCB0cnVlY2xhc3MpWyJBUkkiXQogIAogIHNjM19yZXNmbCA8LSBTQzNfQ2x1c3Qoc29iajIsIGs9NSwgaW5wdXRfbWFya2Vycz1yb3duYW1lcyhzb2JqMilbaXhzXVtpZHhzc2w0XSkgCiAgdHJ1ZWNsYXNzIDwtIGNvbERhdGEoc2ltLmdyb3VwczMpJEdyb3VwICAKICBhcmlfc2MzX2ZsW2ldIDwtIGV2YWxfQ2x1c3RlcihzYzNfcmVzZmwkY2x1c3RlciwgdHJ1ZWNsYXNzKVsiQVJJIl0KICAKICBzYzNfcmVzc2NtIDwtIFNDM19DbHVzdChzb2JqMiwgaz01LCBpbnB1dF9tYXJrZXJzPXJvd25hbWVzKHNvYmoyKVtpZHhzc2w2XSkgCiAgYXJpX3NjM19zY21baV0gPC0gZXZhbF9DbHVzdGVyKHNjM19yZXNzY20kY2x1c3RlciwgdHJ1ZWNsYXNzKVsiQVJJIl0KICAgIH0gCn0gCnJlc3VsdHMgPC0gbGlzdChhcmlfc3NoLCBhcmlfc2V1cmF0LCBhcmlfZmVhc3RmbCwgYXJpX3NwYXJzZSwgYXJpX3NjbSwgYXJpX3NjM19zZXVyYXQsIGFyaV9zYzNfbGFzc28sIGFyaV9zYzNfc3NsLCBhcmlfc2MzX2ZsLCBhcmlfc2MzX3NjbSkgICAKcmV0dXJuKHJlc3VsdHMpIAp9IAoKI2RvaW5nIDEwIHNpbXVsYXRpb25zIApjb21wYXJlX21ldCgxMDAsIDIwMDAsIDIwMCwgc2MzID0gVFJVRSkgCgojIDYgbW9yZSAKCmBgYAoKIyMgU2ltdWxhdGlvbiByZXN1bHRzIApGaWd1cmUgMSA6IFNIQy1TU0wgYW5kIFNIQy1GTCBwZXJmb3JtZWQgYmV0dGVyIHRoYW4gU2V1cmF0IGFuZCBTSEMgaW4gY2x1c3RlcmluZyBkYXRhIHdpdGggcmFyZSBjZWxsIHBvcHVsYXRpb25zwqAgKGR1ZSB0byBjb21wdXRhdGlvbiwgdGhpcyBpcyBub3QgZGlzcGxheWVkIGhlcmUsIHBsZWFzZSByZWZlciB0byBQUFQpIAoKRmlndXJlIDI6IFNIQy1TU0wgYW5kIFNIQy1GTCBzaW1pbGFybHkgcGVyZm9ybWVkIGJldHRlciB0aGFuIFNIQyB1c2luZyBTQzMgY2x1c3RlcmluZ8KgIChkdWUgdG8gY29tcHV0YXRpb24sIHRoaXMgaXMgbm90IGRpc3BsYXllZCBoZXJlLCBwbGVhc2UgcmVmZXIgdG8gUFBUKSAKCgojIENvbXBhcmluZyBmZWF0dXJlIHNlbGVjdGlvbiBtZXRob2RzIHdpdGggcmVhbCBkYXRhIC0gVGFidWxhIFNhcGllbnMgaHVtYW4ga2lkbmV5IGNlbGxzIGRhdGEgCgpDaGFsbGVuZ2VzIC0gCjcgY2VsbCB0eXBlcyA6wqBLaWRuZXkgZXBpdGhlbGlhbCBjZWxsLCBCIGNlbGwsIENENCBUIGNlbGwsIENEOCBUIGNlbGwsIE5LIGNlbGwswqBNYWNyb3BhZ2VzIGFuZMKgRW5kb3RoZWxpYWwgY2VsbMKgCi0+IG1vcmUgdGhhbiA4MDAwIG91dCBvZiA5MDAwIGNlbGxzIGFyZSBraWRuZXkgZXBpdGhlbGlhbCBjZWxscywgU2V1cmF0IHBlcmZvcm1zIHBvb3JseSBpbiBjbHVzdGVyaW5nIHJhcmUgY2VsbCBwb3B1bGF0aW9uc8KgCgpnYXAgc3RhdGlzdGljIAoKYGBge3J9Cm91dCA8LSByZWFkUkRTKCJzY1JOQV9zaGNfc3NsX291dC5yZHMiKSAKcGxvdChvdXQkd19sMG5vcm0sCiAgICAgb3V0JGdhcHNfbWVhbiwKICAgICBsb2cgPSAieCIsCiAgICAgeGxhYiA9ICIjIE5vbi16ZXJvIEZlYXR1cmVzIiwKICAgICB5bGFiID0gIkdhcCBTdGF0aXN0aWNzIiwKICAgICB5bGltID0gYyhtaW4ob3V0JGdhcHNfbWVhbiAtIG91dCRnYXBzX3NlKSAtIDAuMDAwMSwKICAgICAgICAgICAgICBtYXgob3V0JGdhcHNfbWVhbiArIG91dCRnYXBzX3NlKSArIDAuMDAwMSksCiAgICAgdHlwZSA9ICJsIiwKICAgICBsd2QgPSAxKQphcnJvd3MoeDAgPSBvdXQkd19sMG5vcm0sCiAgICAgICB5MCA9IG91dCRnYXBzX21lYW4gLSBvdXQkZ2Fwc19zZSwKICAgICAgIHgxID0gb3V0JHdfbDBub3JtLAogICAgICAgeTEgPSBvdXQkZ2Fwc19tZWFuICsgb3V0JGdhcHNfc2UsCiAgICAgICBjb2RlID0gMywgYW5nbGUgPSA5MCwgbGVuZ3RoID0gMC4wMiwgbHdkID0gMSkKYGBgCgpzZWxlY3RpbmcgdGhlIG5vbi16ZXJvIHdlaWdodCBmZWF0dXJlcyBmb3IgcmVjb21iaW5lIApgYGB7cn0KdyA8LSBvdXQkcmVzdWx0JHcKbmFtZXModykgPC0gY29sbmFtZXMobXRfZXhwcikKCncgPC0gc29ydCh3LCBkZWNyZWFzaW5nID0gVFJVRSkKd19ub256ZXJvIDwtIHdbdyA+IDBdCgp0YiA8LSB0aWJibGUoZmVhdHVyZSA9IG5hbWVzKHcpLAogICAgICAgICAgICAgdyA9IHcpCnRiIDwtIHRiICU+JQogIG11dGF0ZShpID0gMTpucm93KHRiKSkgJT4lCiAgbXV0YXRlKGxhYmVsID0gaWZlbHNlKGkgPD0gMTAsIGZlYXR1cmUsICIiKSkKCm9wdGlvbnMoZ2dyZXBlbC5tYXgub3ZlcmxhcHMgPSBJbmYpCmdnbGluZSh0YiwgImkiLCAidyIsCiAgICAgICAgICAgIHhsYWIgPSAiZmVhdHVyZSBpbmRleCIsCiAgICAgICAgICAgIGxhYmVsID0gImxhYmVsIiwKICAgICAgICAgICAgcmVwZWwgPSBUUlVFLAogICAgICAgICAgICBsYWJlbC5yZWN0YW5nbGUgPSBUUlVFLAogICAgICAgICAgICBwb2ludC5zaXplID0gMC4xLAogICAgICAgICAgICBwbG90X3R5cGUgPSAicCIpCmBgYAoKIyMgU2V1cmF0J3MgYnVpbHQgaW4gZmVhdHVyZSBzZWxlY3Rpb24gbWV0aG9kICh2c3QpCmBgYHtyfQpsaWJyYXJ5KFNldXJhdCkKI25vcm1hbGl6ZSAKa2lkYXRhIDwtIE5vcm1hbGl6ZURhdGEoa2lkYXRhKQoKI25vdywgdXNlIGJsb29kMSBmb3IgSFZGIHNlbGVjdGVkIGJ5IFNldXJhdCwgYW5kIGJsb29kMiBmb3Igb25lcyBzZWxlY3RlZCBieSBGRUFTVApraWRhdGEgPC0gRmluZFZhcmlhYmxlRmVhdHVyZXMoa2lkYXRhLCBzZWxlY3Rpb24ubWV0aG9kID0gInZzdCIsIG5mZWF0dXJlcyA9IDIwMDApCgphbGwuZ2VuZXMgPC0gcm93bmFtZXMoa2lkYXRhKSAKa2lkYXRhIDwtIFNjYWxlRGF0YShraWRhdGEsIGZlYXR1cmVzPWFsbC5nZW5lcykKI2lmIHVzaW5nIEZFQVNUIHNob3VsZCBpbnB1dCBzZWxlY3RlZCBmZWF0dXJlcyBoZXJlIApraWRhdGExIDwtIFJ1blBDQShraWRhdGEsIGZlYXR1cmVzPVZhcmlhYmxlRmVhdHVyZXMob2JqZWN0PWtpZGF0YSkpCmBgYAoKYGBge3J9CkVsYm93UGxvdChraWRhdGExKSAjdXNlIDE4IFBDcyAKYGBgCgpgYGB7cn0Ka2lkYXRhMSA8LSBGaW5kTmVpZ2hib3JzKGtpZGF0YTEsIGRpbXM9MToxNSkKCmtpZGF0YTEgPC0gRmluZENsdXN0ZXJzKGtpZGF0YTEsIHJlc29sdXRpb24gPSAwLjE4KSAKdHJ1ZWNsYXNzIDwtIGtpZGF0YUBtZXRhLmRhdGEkZnJlZV9hbm5vdGF0aW9uCmBgYAoKIyMjIGV2YWx1YXRpbmcgdGhlIHBlcmZvcm1hbmNlIG9mIFNldXJhdCdzIGJ1aWx0IGluIGZlYXR1cmUgc2VsZWN0aW9uIG1ldGhvZCAodnN0KQpgYGB7cn0KbGlicmFyeShGRUFTVCkKa2lfc2V1cmF0PC1ldmFsX0NsdXN0ZXIoa2lkYXRhMUBtZXRhLmRhdGEkc2V1cmF0X2NsdXN0ZXJzLCB0cnVlY2xhc3MpIAoKbGlicmFyeShrbml0cikKa2FibGUoa2lfc2V1cmF0LCBjYXB0aW9uID0gIkNsdXN0ZXIgRXZhbHVhdGlvbiBNZXRyaWNzIikKYGBgCiMjIyBVTUFQICh3aXRoIHRydWUgbGFiZWxzKSAKYGBge3J9CnNldC5zZWVkKDEpCmtpZGF0YTEgPC0gUnVuVU1BUChraWRhdGExLCBkaW1zPTE6NTApIApEaW1QbG90KGtpZGF0YTEsIHJlZHVjdGlvbj0idW1hcCIpCmBgYAoKCmBgYHtyfQojIFN0ZXAgMTogQWRkIHRydWUgY2xhc3MgYW5kIGNsdXN0ZXJpbmcgbGFiZWxzIHRvIHRoZSBtZXRhZGF0YQpraWRhdGExJHRydWVjbGFzcyA8LSBraWRhdGExQG1ldGEuZGF0YSRmcmVlX2Fubm90YXRpb24KCiMgU3RlcCAyOiBFeHRyYWN0IFVNQVAgY29vcmRpbmF0ZXMgYW5kIG1ldGFkYXRhCnVtYXBfZGF0YSA8LSBhcy5kYXRhLmZyYW1lKEVtYmVkZGluZ3Moa2lkYXRhMSwgInVtYXAiKSkgICMgRXh0cmFjdCBVTUFQIGVtYmVkZGluZ3MKY29sbmFtZXModW1hcF9kYXRhKSA8LSBjKCJVTUFQXzEiLCAiVU1BUF8yIikgICAgICAgICAgICAgIyBSZW5hbWUgY29sdW1ucwp1bWFwX2RhdGEkc2V1cmF0X2NsdXN0ZXJzIDwtIGtpZGF0YTEkc2V1cmF0X2NsdXN0ZXJzICAgICAgIyBBZGQgY2x1c3RlciBsYWJlbHMKdW1hcF9kYXRhJHRydWVjbGFzcyA8LSBraWRhdGExJHRydWVjbGFzcyAgICAgICAgICAgICAgICAgICMgQWRkIHRydWUgY2xhc3MgbGFiZWxzCgojIFN0ZXAgMzogUGxvdCBVTUFQIHdpdGggb3ZlcmxheWVkIHRydWUgY2xhc3MgbGFiZWxzCmdncGxvdCh1bWFwX2RhdGEsIGFlcyh4ID0gVU1BUF8xLCB5ID0gVU1BUF8yKSkgKwogIGdlb21fcG9pbnQoYWVzKGNvbG9yID0gYXMuZmFjdG9yKHNldXJhdF9jbHVzdGVycykpLCBhbHBoYSA9IDAuNiwgc2l6ZSA9IDIpICsgIyBQb2ludHMgZm9yIGNsdXN0ZXJzCiAgZ2VvbV90ZXh0KGFlcyhsYWJlbCA9IHRydWVjbGFzcyksIHNpemUgPSAzLCB2anVzdCA9IC0xLCBjaGVja19vdmVybGFwID0gVFJVRSkgKyAjIFRleHQgb3ZlcmxheSBmb3IgdHJ1ZSBjbGFzcwogIGxhYnMoCiAgICBjb2xvciA9ICJDbHVzdGVyIiwgCiAgICB4ID0gIlVNQVAgMSIsCiAgICB5ID0gIlVNQVAgMiIsCiAgICB0aXRsZSA9ICJVTUFQOiBDbHVzdGVyaW5nIFJlc3VsdHMgd2l0aCBUcnVlIENsYXNzIE92ZXJsYXkiCiAgKSArCiAgdGhlbWVfbWluaW1hbCgpICsKICB0aGVtZSgKICAgIGxlZ2VuZC5wb3NpdGlvbiA9ICJyaWdodCIsICAgICAgICAgICMgQWRqdXN0IGxlZ2VuZCBwb3NpdGlvbgogICAgcGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkgICMgQ2VudGVyIHRoZSB0aXRsZQogICkKYGBgCgoKCiMjIFNwYXJzZSBIaWVyYXJjaGlhbCBDbHVzdGVyaW5nIChTSEMpIApgYGB7cn0KI25vcm1hbGl6ZSAKWTEgPC0gYXMubWF0cml4KFkxKQoKbGlicmFyeShkcGx5cikKdG90X21lZCA8LSBjb2xTdW1zKFkxKSAlPiUKICBtZWRpYW4oKQpub3JtMSA8LSBmdW5jdGlvbih2ZWMpIHsKICB2ZWMvc3VtKHZlYykKfQpZMSA8LSBhcHBseShZMSwgMiwgbm9ybTEpClkxIDwtIFkxICogdG90X21lZApZMSA8LSBZMSArIDAuMQpZMSA8LSB0KFkxKSAKClkxIDwtIGxvZzIoWTEgLSBtaW4oWTEpICsgMSkKdGIgPC0gdGliYmxlKGNlbGwgPSByb3duYW1lcyhZMSkpICU+JQogIGJpbmRfY29scyhhc190aWJibGUoWTEpKSAKCnQgPC0gYXMubWF0cml4KHRiWywtMV0pCnJvd25hbWVzKHQpIDwtIHRiJGNlbGwKCiMgY2VudGVyIGZvciBlYWNoIGZlYXR1cmUKdCA8LSBzY2FsZSh0LCBzY2FsZSA9IEZBTFNFKQoKIyBzY2FsZSBzbyB0aGF0IHRoZSBvdmVyYWxsIHZhcmlhbmNlIGlzIHVuaXQgCnQgPC0gdC9zZChhcy5kb3VibGUodCkpIApkaW0odCkKVmlldyh0KQoKc2hjLnBlcm11dGUub3V0IDwtIHNwYXJjbDo6SGllcmFyY2hpY2FsU3BhcnNlQ2x1c3Rlci5wZXJtdXRlKHggPSB0LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbnBlcm1zID0gMywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHdib3VuZHMgPSBzZXEoMS4xLCAxMCwgbGVuID0gMTAwKSkKCgp3MyA8LSBzaGMucGVybXV0ZS5vdXQkcmVzdWx0JHcKCm5hbWVzKHczKSA8LSBjb2xuYW1lcyh0KQoKdzMgPC0gc29ydCh3MywgZGVjcmVhc2luZyA9IFRSVUUpCnczX25vbnplcm8gPC0gdzNbdzMgPiAwXQoKbmFtZXMgPC0gYXR0cih3M19ub256ZXJvLCAibmFtZXMiKQppZHhzc2w0IDwtIG1hdGNoKG5hbWVzLCByb3duYW1lcyhZKSkKbGVuZ3RoKGlkeHNzbDQpIAojZGF0YSA8LSBjb3VudHMoc2ltLmdyb3VwczMpIApsaWJyYXJ5KFNldXJhdCkKCmRhdGEgPC0gQ3JlYXRlU2V1cmF0T2JqZWN0KGNvdW50cyA9IFksCiAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbi5mZWF0dXJlcyA9IDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbi5jZWxscyA9IDApCmRhdGEgPC0gTm9ybWFsaXplRGF0YShkYXRhKQojIHNldCB2YXJpYWJsZSBnZW5lcyBhcyBhbGwgZGlzY3JpbWluYW50IG1hcmtlcnMKI1ZhcmlhYmxlRmVhdHVyZXMoZGF0YSkgPC0gcm93bmFtZXMoZGF0YSkKIyBTY2FsaW5nIHRoZSBkYXRhCnNvYmogPC0gU2NhbGVEYXRhKGRhdGEsIGZlYXR1cmVzID0gcm93bmFtZXMoZGF0YSkpIAojIFBlcmZvcm0gbGluZWFyIGRpbWVuc2lvbmFsIHJlZHVjdGlvbgoKIyNGb3IgU0hDLVNTTCAtIApraWRhdGE0IDwtIFJ1blBDQShzb2JqLCBmZWF0dXJlcyA9IHJvd25hbWVzKGRhdGEpW2lkeHNzbDRdKSAKCmtpZGF0YTQgPC0gRmluZE5laWdoYm9ycyhraWRhdGEyLCBkaW1zPTE6MjApICAKa2lkYXRhNCA8LSBGaW5kQ2x1c3RlcnMoa2lkYXRhMiwgcmVzb2x1dGlvbj0wLjE2KQoKa2lkYXRhNCR0cnVlY2xhc3MgPC0ga2lkYXRhMUBtZXRhLmRhdGEkZnJlZV9hbm5vdGF0aW9uCgpraV9zaGM8LWV2YWxfQ2x1c3RlcihraWRhdGE0QG1ldGEuZGF0YSRzZXVyYXRfY2x1c3RlcnMsIHRydWVjbGFzcykKYGBgCgpgYGB7cn0Ka2lkYXRhNCA8LSBGaW5kTmVpZ2hib3JzKGtpZGF0YTQsIGRpbXM9MToxNSkKYGBgCgpgYGB7cn0Ka2lkYXRhNCA8LSBGaW5kQ2x1c3RlcnMoa2lkYXRhNCwgcmVzb2x1dGlvbiA9IDAuMTIpIAp0cnVlY2xhc3MgPC0ga2lkYXRhQG1ldGEuZGF0YSRmcmVlX2Fubm90YXRpb24KYGBgCgojIyMgZXZhbHVhdGluZyBwZXJmb3JtYW5jZSB3aXRoIFNIQyAKYGBge3J9CmxpYnJhcnkoRkVBU1QpCmtpX3NoYzwtZXZhbF9DbHVzdGVyKGtpZGF0YTRAbWV0YS5kYXRhJHNldXJhdF9jbHVzdGVycywgdHJ1ZWNsYXNzKSAKCmxpYnJhcnkoa25pdHIpCmthYmxlKGtpX3NoYywgY2FwdGlvbiA9ICJDbHVzdGVyIEV2YWx1YXRpb24gTWV0cmljcyIpCmBgYAoKIyMjIFVNQVAgKHdpdGggdHJ1ZSBsYWJlbHMpIApgYGB7cn0Kc2V0LnNlZWQoMSkKa2lkYXRhNCA8LSBSdW5VTUFQKGtpZGF0YTQsIGRpbXM9MTo1MCkgCmBgYAoKYGBge3J9CkRpbVBsb3Qoa2lkYXRhNCwgcmVkdWN0aW9uPSJ1bWFwIikgCmBgYAoKCmBgYHtyfQpsaWJyYXJ5KGdncGxvdDIpCiMgU3RlcCAxOiBBZGQgdHJ1ZSBjbGFzcyBhbmQgY2x1c3RlcmluZyBsYWJlbHMgdG8gdGhlIG1ldGFkYXRhCmtpZGF0YTQkdHJ1ZWNsYXNzIDwtIGtpZGF0YTFAbWV0YS5kYXRhJGZyZWVfYW5ub3RhdGlvbgoKIyBTdGVwIDI6IEV4dHJhY3QgVU1BUCBjb29yZGluYXRlcyBhbmQgbWV0YWRhdGEKdW1hcF9kYXRhIDwtIGFzLmRhdGEuZnJhbWUoRW1iZWRkaW5ncyhraWRhdGE0LCAidW1hcCIpKSAgIyBFeHRyYWN0IFVNQVAgZW1iZWRkaW5ncwpjb2xuYW1lcyh1bWFwX2RhdGEpIDwtIGMoIlVNQVBfMSIsICJVTUFQXzIiKSAgICAgICAgICAgICAjIFJlbmFtZSBjb2x1bW5zCnVtYXBfZGF0YSRzZXVyYXRfY2x1c3RlcnMgPC0ga2lkYXRhNCRzZXVyYXRfY2x1c3RlcnMgICAgICAjIEFkZCBjbHVzdGVyIGxhYmVscwp1bWFwX2RhdGEkdHJ1ZWNsYXNzIDwtIGtpZGF0YTQkdHJ1ZWNsYXNzICAgICAgICAgICAgICAgICAgIyBBZGQgdHJ1ZSBjbGFzcyBsYWJlbHMKCiMgU3RlcCAzOiBQbG90IFVNQVAgd2l0aCBvdmVybGF5ZWQgdHJ1ZSBjbGFzcyBsYWJlbHMKZ2dwbG90KHVtYXBfZGF0YSwgYWVzKHggPSBVTUFQXzEsIHkgPSBVTUFQXzIpKSArCiAgZ2VvbV9wb2ludChhZXMoY29sb3IgPSBhcy5mYWN0b3Ioc2V1cmF0X2NsdXN0ZXJzKSksIGFscGhhID0gMC42LCBzaXplID0gMikgKyAjIFBvaW50cyBmb3IgY2x1c3RlcnMKICBnZW9tX3RleHQoYWVzKGxhYmVsID0gdHJ1ZWNsYXNzKSwgc2l6ZSA9IDMsIHZqdXN0ID0gLTEsIGNoZWNrX292ZXJsYXAgPSBUUlVFKSArICMgVGV4dCBvdmVybGF5IGZvciB0cnVlIGNsYXNzCiAgbGFicygKICAgIGNvbG9yID0gIkNsdXN0ZXIiLCAKICAgIHggPSAiVU1BUCAxIiwKICAgIHkgPSAiVU1BUCAyIiwKICAgIHRpdGxlID0gIlVNQVA6IENsdXN0ZXJpbmcgUmVzdWx0cyB3aXRoIFRydWUgQ2xhc3MgT3ZlcmxheSIKICApICsKICB0aGVtZV9taW5pbWFsKCkgKwogIHRoZW1lKAogICAgbGVnZW5kLnBvc2l0aW9uID0gInJpZ2h0IiwgICAgICAgICAgIyBBZGp1c3QgbGVnZW5kIHBvc2l0aW9uCiAgICBwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSAgIyBDZW50ZXIgdGhlIHRpdGxlCiAgKQpgYGAKCgojIyBSRUNPTUJJTkUgU0hDLVNTTCBhbGdvcml0aG0gCmBgYHtyfQojbm9ybWFsaXplIApZMSA8LSBhcy5tYXRyaXgoWTEpCgpsaWJyYXJ5KGRwbHlyKQp0b3RfbWVkIDwtIGNvbFN1bXMoWTEpICU+JQogIG1lZGlhbigpCm5vcm0xIDwtIGZ1bmN0aW9uKHZlYykgewogIHZlYy9zdW0odmVjKQp9ClkxIDwtIGFwcGx5KFkxLCAyLCBub3JtMSkKWTEgPC0gWTEgKiB0b3RfbWVkClkxIDwtIFkxICsgMC4xClkxIDwtIHQoWTEpIAoKWTEgPC0gbG9nMihZMSAtIG1pbihZMSkgKyAxKQp0YiA8LSB0aWJibGUoY2VsbCA9IHJvd25hbWVzKFkxKSkgJT4lCiAgYmluZF9jb2xzKGFzX3RpYmJsZShZMSkpIAoKdCA8LSBhcy5tYXRyaXgodGJbLC0xXSkKcm93bmFtZXModCkgPC0gdGIkY2VsbAoKIyBjZW50ZXIgZm9yIGVhY2ggZmVhdHVyZQp0IDwtIHNjYWxlKHQsIHNjYWxlID0gRkFMU0UpCgojIHNjYWxlIHNvIHRoYXQgdGhlIG92ZXJhbGwgdmFyaWFuY2UgaXMgdW5pdCAKdCA8LSB0L3NkKGFzLmRvdWJsZSh0KSkgCmRpbSh0KQpWaWV3KHQpCgpucGVybXMgPSAzIApsYW1iZGExIDwtIDAuMDAwMQpsYW1iZGEwcyA8LSBzZXEoMC4wMDEsIDEwMDAsIGxlbmd0aCA9IDEwMCkKbGlicmFyeShyZWNvbWJpbmUpIAojIAojICMgdGhpcyBpcyB0aGUgbW9zdCBjb3N0bHkgY29tcHV0YXRpb24gaW4gUkVDT01CSU5FCiNzZXQuc2VlZCgxKSAgICMjaW1wb3J0YW50ISEgCmxpYnJhcnkocmVjb21iaW5lKQpvdXQzIDwtIFNIQ19TU0xfZ2Fwc3RhdCh4ID0gdCwKICAgICAgICAgICAgICAgICAgICAgICAgbnBlcm1zID0gbnBlcm1zLAogICAgICAgICAgICAgICAgICAgICAgICBsYW1iZGEwcyA9IGxhbWJkYTBzLAogICAgICAgICAgICAgICAgICAgICAgICBsYW1iZGExID0gbGFtYmRhMSkKCgp3MiA8LSBvdXQzJHJlc3VsdCR3CgpuYW1lcyh3MikgPC0gY29sbmFtZXModCkKCncyIDwtIHNvcnQodzIsIGRlY3JlYXNpbmcgPSBUUlVFKQp3Ml9ub256ZXJvIDwtIHcyW3cyID4gMF0KCm5hbWVzIDwtIGF0dHIodzJfbm9uemVybywgIm5hbWVzIikKaWR4c3NsMyA8LSBtYXRjaChuYW1lcywgcm93bmFtZXMoWSkpCmxlbmd0aChpZHhzc2wzKQojZGF0YSA8LSBjb3VudHMoc2ltLmdyb3VwczMpIApsaWJyYXJ5KFNldXJhdCkKCmRhdGEgPC0gQ3JlYXRlU2V1cmF0T2JqZWN0KGNvdW50cyA9IFksCiAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbi5mZWF0dXJlcyA9IDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbi5jZWxscyA9IDApCmRhdGEgPC0gTm9ybWFsaXplRGF0YShkYXRhKQojIHNldCB2YXJpYWJsZSBnZW5lcyBhcyBhbGwgZGlzY3JpbWluYW50IG1hcmtlcnMKI1ZhcmlhYmxlRmVhdHVyZXMoZGF0YSkgPC0gcm93bmFtZXMoZGF0YSkKIyBTY2FsaW5nIHRoZSBkYXRhCnNvYmogPC0gU2NhbGVEYXRhKGRhdGEsIGZlYXR1cmVzID0gcm93bmFtZXMoZGF0YSkpIAojIFBlcmZvcm0gbGluZWFyIGRpbWVuc2lvbmFsIHJlZHVjdGlvbgoKIyNGb3IgU0hDLVNTTCAtIApraWRhdGEyIDwtIFJ1blBDQShzb2JqLCBmZWF0dXJlcyA9IHJvd25hbWVzKGRhdGEpW2lkeHNzbDNdKSAKCmtpZGF0YTIgPC0gRmluZE5laWdoYm9ycyhraWRhdGEyLCBkaW1zPTE6MjApICAKa2lkYXRhMiA8LSBGaW5kQ2x1c3RlcnMoa2lkYXRhMiwgcmVzb2x1dGlvbj0wLjE2KQoKa2lkYXRhMiR0cnVlY2xhc3MgPC0ga2lkYXRhMUBtZXRhLmRhdGEkZnJlZV9hbm5vdGF0aW9uCgpraV9yZWNvbWJpbmU8LWV2YWxfQ2x1c3RlcihraWRhdGEyQG1ldGEuZGF0YSRzZXVyYXRfY2x1c3RlcnMsIHRydWVjbGFzcykKYGBgCgojIyMgZXZhbHVhdGluZyBTSEMtU1NMIHBlcmZvcm1hbmNlIAoKYGBge3J9CmthYmxlKGtpX3JlY29tYmluZSwgY2FwdGlvbiA9ICJDbHVzdGVyIEV2YWx1YXRpb24gTWV0cmljcyIpICAKYGBgCiMjIyBVTUFQICh3aXRoIHRydWUgbGFiZWxzKSAKCmBgYHtyfQpraWRhdGEzIDwtIFJ1blVNQVAoa2lkYXRhMywgZmVhdHVyZXM9cm93bmFtZXMoZGF0YSlbaWR4c3NsM10pIApgYGAKCmBgYHtyfQpEaW1QbG90KGtpZGF0YTMsIHJlZHVjdGlvbj0idW1hcCIpIApgYGAKCgpgYGB7cn0KIyBTdGVwIDE6IEFkZCB0cnVlIGNsYXNzIGFuZCBjbHVzdGVyaW5nIGxhYmVscyB0byB0aGUgbWV0YWRhdGEKa2lkYXRhMyR0cnVlY2xhc3MgPC0ga2lkYXRhMUBtZXRhLmRhdGEkZnJlZV9hbm5vdGF0aW9uCgojIFN0ZXAgMjogRXh0cmFjdCBVTUFQIGNvb3JkaW5hdGVzIGFuZCBtZXRhZGF0YQp1bWFwX2RhdGEgPC0gYXMuZGF0YS5mcmFtZShFbWJlZGRpbmdzKGtpZGF0YTMsICJ1bWFwIikpICAjIEV4dHJhY3QgVU1BUCBlbWJlZGRpbmdzCmNvbG5hbWVzKHVtYXBfZGF0YSkgPC0gYygiVU1BUF8xIiwgIlVNQVBfMiIpICAgICAgICAgICAgICMgUmVuYW1lIGNvbHVtbnMKdW1hcF9kYXRhJHNldXJhdF9jbHVzdGVycyA8LSBraWRhdGEzJHNldXJhdF9jbHVzdGVycyAgICAgICMgQWRkIGNsdXN0ZXIgbGFiZWxzCnVtYXBfZGF0YSR0cnVlY2xhc3MgPC0ga2lkYXRhMyR0cnVlY2xhc3MgICAgICAgICAgICAgICAgICAjIEFkZCB0cnVlIGNsYXNzIGxhYmVscwoKIyBTdGVwIDM6IFBsb3QgVU1BUCB3aXRoIG92ZXJsYXllZCB0cnVlIGNsYXNzIGxhYmVscwpnZ3Bsb3QodW1hcF9kYXRhLCBhZXMoeCA9IFVNQVBfMSwgeSA9IFVNQVBfMikpICsKICBnZW9tX3BvaW50KGFlcyhjb2xvciA9IGFzLmZhY3RvcihzZXVyYXRfY2x1c3RlcnMpKSwgYWxwaGEgPSAwLjYsIHNpemUgPSAyKSArICMgUG9pbnRzIGZvciBjbHVzdGVycwogIGdlb21fdGV4dChhZXMobGFiZWwgPSB0cnVlY2xhc3MpLCBzaXplID0gMywgdmp1c3QgPSAtMSwgY2hlY2tfb3ZlcmxhcCA9IFRSVUUpICsgIyBUZXh0IG92ZXJsYXkgZm9yIHRydWUgY2xhc3MKICBsYWJzKAogICAgY29sb3IgPSAiQ2x1c3RlciIsIAogICAgeCA9ICJVTUFQIDEiLAogICAgeSA9ICJVTUFQIDIiLAogICAgdGl0bGUgPSAiVU1BUDogQ2x1c3RlcmluZyBSZXN1bHRzIHdpdGggVHJ1ZSBDbGFzcyBPdmVybGF5IgogICkgKwogIHRoZW1lX21pbmltYWwoKSArCiAgdGhlbWUoCiAgICBsZWdlbmQucG9zaXRpb24gPSAicmlnaHQiLCAgICAgICAgICAjIEFkanVzdCBsZWdlbmQgcG9zaXRpb24KICAgIHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpICAjIENlbnRlciB0aGUgdGl0bGUKICApIApgYGAKCiMjIFNDTWFya2VyIGFsZ29yaXRobSAKYGBge3J9CmxpYnJhcnkoU0NNYXJrZXIpCmRpbShZKSAKWTE8LWxvZyhZKzEpIAoKcmVzPU1vZGFsRmlsdGVyKGRhdGE9WTEsZ2VuZUs9MTAsY2VsbEs9MTAsd2lkdGg9MikgCnJlcz1HZW5lRmlsdGVyKG9iaj1yZXMpCnJlcz1nZXRNYXJrZXIob2JqPXJlcyxrPTMwMCxuPTMwKSAKaGVhZChyZXMkbWFya2VyKSAKbGVuZ3RoKHJlcyRtYXJrZXIpICM5MzggCmBgYAoKIyMjIGV2YWx1YXRpbmcgcGVyZm9ybWFuY2Ugb2YgU0NNYXJrZXIgIApgYGB7cn0Ka2lkYXRhMyA8LSBSdW5QQ0Eoa2lkYXRhMiwgZmVhdHVyZXMgPSByZXMkbWFya2VyKSAKCmtpZGF0YTMgPC0gRmluZE5laWdoYm9ycyhraWRhdGEzLCBkaW1zPTE6MjApICAKa2lkYXRhMyA8LSBGaW5kQ2x1c3RlcnMoa2lkYXRhMywgcmVzb2x1dGlvbiA9IDAuMTIpCmtpZGF0YTMkdHJ1ZWNsYXNzIDwtIGtpZGF0YTFAbWV0YS5kYXRhJGZyZWVfYW5ub3RhdGlvbgpraV9zY21hcmtlcjwtZXZhbF9DbHVzdGVyKGtpZGF0YTNAbWV0YS5kYXRhJHNldXJhdF9jbHVzdGVycywga2lkYXRhMyR0cnVlY2xhc3MpCmBgYAoKYGBge3J9CiNraWRhdGEyJHRydWVjbGFzcyA8LSBraWRhdGExQG1ldGEuZGF0YSRmcmVlX2Fubm90YXRpb24KI2tpX3JlY29tYmluZTwtZXZhbF9DbHVzdGVyKGtpZGF0YTJAbWV0YS5kYXRhJHNldXJhdF9jbHVzdGVycywgdHJ1ZWNsYXNzKSAKa2FibGUoa2lfc2NtYXJrZXIsIGNhcHRpb24gPSAiQ2x1c3RlciBFdmFsdWF0aW9uIE1ldHJpY3MiKSAKYGBgCgojIyMgVU1BUCAod2l0aCB0cnVlIGxhYmVscykKYGBge3J9CiNraWRhdGEyIDwtIFJ1blVNQVAoa2lkYXRhMiwgZmVhdHVyZXM9Z2VuZXMpIApEaW1QbG90KGtpZGF0YTIsIHJlZHVjdGlvbj0idW1hcCIpIApgYGAKCmBgYHtyfQojIFN0ZXAgMTogQWRkIHRydWUgY2xhc3MgYW5kIGNsdXN0ZXJpbmcgbGFiZWxzIHRvIHRoZSBtZXRhZGF0YQpraWRhdGEyJHRydWVjbGFzcyA8LSBraWRhdGExQG1ldGEuZGF0YSRmcmVlX2Fubm90YXRpb24KCiMgU3RlcCAyOiBFeHRyYWN0IFVNQVAgY29vcmRpbmF0ZXMgYW5kIG1ldGFkYXRhCnVtYXBfZGF0YSA8LSBhcy5kYXRhLmZyYW1lKEVtYmVkZGluZ3Moa2lkYXRhMiwgInVtYXAiKSkgICMgRXh0cmFjdCBVTUFQIGVtYmVkZGluZ3MKY29sbmFtZXModW1hcF9kYXRhKSA8LSBjKCJVTUFQXzEiLCAiVU1BUF8yIikgICAgICAgICAgICAgIyBSZW5hbWUgY29sdW1ucwp1bWFwX2RhdGEkc2V1cmF0X2NsdXN0ZXJzIDwtIGtpZGF0YTIkc2V1cmF0X2NsdXN0ZXJzICAgICAgIyBBZGQgY2x1c3RlciBsYWJlbHMKdW1hcF9kYXRhJHRydWVjbGFzcyA8LSBraWRhdGEyJHRydWVjbGFzcyAgICAgICAgICAgICAgICAgICMgQWRkIHRydWUgY2xhc3MgbGFiZWxzCgojIFN0ZXAgMzogUGxvdCBVTUFQIHdpdGggb3ZlcmxheWVkIHRydWUgY2xhc3MgbGFiZWxzCmdncGxvdCh1bWFwX2RhdGEsIGFlcyh4ID0gVU1BUF8xLCB5ID0gVU1BUF8yKSkgKwogIGdlb21fcG9pbnQoYWVzKGNvbG9yID0gYXMuZmFjdG9yKHNldXJhdF9jbHVzdGVycykpLCBhbHBoYSA9IDAuNiwgc2l6ZSA9IDIpICsgIyBQb2ludHMgZm9yIGNsdXN0ZXJzCiAgZ2VvbV90ZXh0KGFlcyhsYWJlbCA9IHRydWVjbGFzcyksIHNpemUgPSAzLCB2anVzdCA9IC0xLCBjaGVja19vdmVybGFwID0gVFJVRSkgKyAjIFRleHQgb3ZlcmxheSBmb3IgdHJ1ZSBjbGFzcwogIGxhYnMoCiAgICBjb2xvciA9ICJDbHVzdGVyIiwgCiAgICB4ID0gIlVNQVAgMSIsCiAgICB5ID0gIlVNQVAgMiIsCiAgICB0aXRsZSA9ICJVTUFQOiBDbHVzdGVyaW5nIFJlc3VsdHMgd2l0aCBUcnVlIENsYXNzIE92ZXJsYXkiCiAgKSArCiAgdGhlbWVfbWluaW1hbCgpICsKICB0aGVtZSgKICAgIGxlZ2VuZC5wb3NpdGlvbiA9ICJyaWdodCIsICAgICAgICAgICMgQWRqdXN0IGxlZ2VuZCBwb3NpdGlvbgogICAgcGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkgICMgQ2VudGVyIHRoZSB0aXRsZQogICkgCmBgYAoKCiMjIENvbXBhcmUgdGhlIGZvdXIgbWV0aG9kcyBpbiBjbHVzdGVyaW5nIGFjY3VyYWN5IApgYGB7cn0KcmVzX2NvbXBhcmU8LWNiaW5kKGtpX3NldXJhdCwga2lfcmVjb21iaW5lLCBraV9zY21hcmtlciwga2lfc2hjKSAKa2FibGUocmVzX2NvbXBhcmUsIGNhcHRpb24gPSAiQ2x1c3RlciBFdmFsdWF0aW9uIE1ldHJpY3MiKSAKYGBgCgpJdCBpcyBzaG93biB0aGF0IHRoZSBTSEMtU1NMIGZlYXR1cmUgc2VsZWN0aW9uIGFsZ29yaXRobSBvdXRwZXJmb3JtcyBib3RoIFNldXJhdCBhbmQgdHJhZGl0aW9uYWwgU0hDLCBhbmQgaXQgaXMgY29tcGFyYWJsZSB0byB0aGUgU0NNYXJrZXIgYWxnb3JpdGhtLiAKCgoKCg==